#pragma once

#include <initializer_list>

/**
 * @file Array.h
 * @author xingyifan
 * @date 2023-01-12 20:20
 * 
 * @description: 动态数组类型
 */

template <class T>
class DynamicArray
{
public:
    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 09:39
     *
     * @description: 内置节点类型
     */

    struct Node
    {
        T value;
        Node *prev;
        Node *next;

        Node(const T &value = T(), Node *prev = nullptr, Node *next = nullptr) : prev(prev), next(next), value(value) {}
    };

protected:
    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 09:40
     *
     * @description: 保有节点头部和数组长度
     */

    int m_size;
    Node *m_head;
    Node *m_tail;

public:
    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 09:41
     *
     * @description: 构造函数
     */

    DynamicArray();                           // 直接构造
    DynamicArray(std::initializer_list<T> l); // 初始化构造
    DynamicArray(const DynamicArray &arr);    // 拷贝构造

    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 10:26
     *
     * @description: 获得数组信息
     */

    int size() const { return m_size; }
    bool empty() const { return (m_size == 0) ? true : false; }

    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 10:04
     *
     * @description: 操作符重载
     */

    T &operator[](int i);      // 获得元素引用，O(n)
    T operator[](int i) const; // 获得元素值，O(n)

    // 拷贝赋值
    void operator=(const DynamicArray &arr);

    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 10:09
     *
     * @description: 索引操作
     */

    T front() const;             // 获得头部元素，O(1)
    T back() const;              // 获得尾部元素，O(1)
    void insert(int i, T value); // 在 i 位置插入元素，O(n)
    void push_back(T value);     // 最后加入元素，O(1)
    void push_front(T value);    // 最前面加入元素，O(1)
    T pop_back();                // 弹出最后一个元素，O(1)
    T pop_front();               // 弹出第一个元素，O(1)
    int find(T value) const;     // 找到元素，O(n)
    bool kill(T value);          // 删除指定元素，O(n)
    T remove(int i);             // 移除指定索引处的元素并返回，O(n)
    void clear();                // 删除数组元素，O(n)

    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2023-01-12 18:58
     *
     * @description: 节点操作
     */

    Node *node(int i) const;           // 获得指定的节点，O(n)
    Node *insert(Node *node, T value); // 在指定节点处插入元素并返回新节点，O(1)
    void remove(Node *node);           // 移除指定节点的元素，O(1)

    /**
     * @file Matrix.h
     * @author xingyifan
     * @date 2022-11-29 10:27
     *
     * @description: 释放内存
     */

    ~DynamicArray();
};